﻿using System;

namespace exercise.树
{
    public class BinarySearchTree<E> : BinaryTree<E>
    {
        protected Comparison<E> comparator; //使用委托
        //protected IComparer<E> comparator;

        public BinarySearchTree() : this(null)
        {
        }
        public BinarySearchTree(Comparison<E> comparer)
        {
            this.comparator = comparer;
        }

        public void Add(E element)
        {
            elementNotNullCheck(element);

            if (root == null)
            {
                root = createNode(element, null);
                size++;

                afterAdd(root);
                return;
            }

            Node<E> node = root;
            //记录父节点和方向
            Node<E> parent = null;
            int cmp = 0;

            while (node != null)
            {
                parent = node;
                cmp = compare(element, node.element);
                if (cmp > 0)
                {
                    node = node.right;
                }
                else if (cmp < 0)
                {
                    node = node.left;
                }
                else
                {
                    //相等直接覆盖
                    return;
                }
            }

            //节点为空，可以加入
            Node<E> newNode = createNode(element, parent);
            if (cmp > 0)
            {
                parent.right = newNode;
            }
            else if (cmp < 0)
            {
                parent.left = newNode;
            }
            size++;

            afterAdd(newNode);
        }

        /// <summary>
        /// 添加后调整
        /// </summary>
        /// <param name="node"></param>
        protected virtual void afterAdd(Node<E> node)
        {
        }
        /// <summary>
        /// 删除后调整
        /// </summary>
        /// <param name="node"></param>
        protected virtual void afterRemove(Node<E> node)
        {
        }

        protected virtual Node<E> createNode(E element, Node<E> parent)
        {
            return new Node<E>(element, parent);
        }

        /// <summary>
        /// el1>el2 返回正数
        /// el1<el2 返回负数
        /// 相等返回0
        /// </summary>
        /// <param name="e1"></param>
        /// <param name="e2"></param>
        /// <returns></returns>
        private int compare(E e1, E e2)
        {
            if (comparator != null)
            {
                return comparator(e1, e2);
                //return comparator.Compare(e1, e2);
            }
            //没有传入比较方法，就强制用元素实现的比较方法
            return ((IComparable<E>)e1).CompareTo(e2);
        }

        /// <summary>
        /// 用前驱或后继节点覆盖原节点
        /// 如果节点度为2，前驱后继只为左右
        /// </summary>
        /// <param name="element"></param>
        public void remove(E element)
        {
            remove(node(element));
        }
        private void remove(Node<E> node)
        {
            if (node == null) return;

            //度为2
            if (node.hasTwoChild())
            {
                Node<E> s = successor(node);
                node.element = s.element;
                node = s;//node变为叶子节点，在后续会被删除
            }

            //删除node节点
            Node<E> replacement = node.left != null ? node.left : node.right;

            if (replacement != null)
            {
                //node度为1
                replacement.parent = node.parent;
                if (node.parent == null)
                {
                    //根节点
                    root = replacement;
                }
                else if (node == node.parent.left)
                {
                    node.parent.left = replacement;
                }
                else if (node == node.parent.right)
                {
                    node.parent.right = replacement;
                }

                // 节点插入后，恢复平衡
                afterRemove(node);
            }
            else if (node.parent == null)
            {
                //根节点
                root = null;

                afterRemove(node);
            }
            else
            {
                //度为0 ，叶子节点
                if (node == node.parent.right)
                {
                    node.parent.right = null;
                }
                else
                {
                    node.parent.left = null;
                }

                afterRemove(node);
            }

        }

        /// <summary>
        /// 根据值找元素
        /// </summary>
        /// <param name="element"></param>
        /// <returns></returns>
        protected Node<E> node(E element)
        {
            Node<E> node = root;
            while (node != null)
            {
                int cmp = compare(element, node.element);

                if (cmp == 0) return node;
                if (cmp > 0)
                {
                    node = node.right;
                }
                else if (cmp < 0)
                {
                    node = node.left;
                }
            }
            return null;
        }

        public bool contains(E element)
        {
            return node(element) != null;
        }

    }
}
